#define _CRT_SECURE_NO_WARNINGS
#include"Tree.h"
#include"Queue.h"
void Preorder(tree* tr)
{
	if (tr == NULL)
	{
		printf("NULL  ");
		return;
	}
	printf("%d  ", tr->x);
	Preorder(tr->left);
	Preorder(tr->right);
}
void Inorder(tree* tr)
{
	if (tr == NULL)
	{
		printf("NULL  ");
		return;
	}
	Inorder(tr->left);
	printf("%d  ", tr->x);
	Inorder(tr->right);
}
void Postorder(tree* tr)
{
	if (tr == NULL)
	{
		printf("NULL  ");
		return;
	}
	Postorder(tr->left);
	Postorder(tr->right);
	printf("%d  ", tr->x);
	
}
tree* BuyNode(TDataType x)
{
	tree* tmp = (tree*)malloc(sizeof(tree));
	tmp->x = x;
	tmp->left = NULL;
	tmp->right = NULL;
	return tmp;
}
int TreeSize(tree* tr,int size)
{
	if (tr == NULL)return size;
	size++;
	size=TreeSize(tr->left,size);
	size=TreeSize(tr->right,size);
	return size;
}
void LevelOrder(tree* tr)
{
	Queue q;
	QueueInit(&q);
	if (tr)QueuePush(&q, tr);
	while (!QueueEmpty(&q))
	{
		tree* root = QueueFront(&q);
		QueuePop(&q);
		printf("%d", root->x);
		if(root->left)QueuePush(&q, root->left);
		if(root->right)QueuePush(&q, root->right);
	}
	
}

void TreeDestory(tree* root)
{
	if (root == NULL)
	{
		return ;
	}
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
	root = NULL;
}

int TreeLeafSize(tree* root)
{
	if (root == NULL)return 0;
	return (root->left == NULL && root->right == NULL)?1:TreeLeafSize(root->left) + TreeLeafSize(root->right);
}


int TreeLevelKSize(tree* root, int k)
{
	Queue q;
	if (root == NULL) return 0;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		k--;
		int size = QueueSize(&q);
		for (int i = 1; i <= size; i++)
		{
			tree* tmp = QueueFront(&q);
			QueuePop(&q);
			if (tmp->left)QueuePush(&q, tmp->left);
			if (tmp->right)QueuePush(&q, tmp->right);
		}
		if (k == 1)return QueueSize(&q);
		
	}
	return 0;
}

tree* BinaryTreeFind(tree* root, TDataType x)
{
	if (root == NULL)return NULL;
	if (root->x == x)return root;
	tree*tml=BinaryTreeFind(root->left, x);
	if (tml != NULL)return tml;
	tree*tmr=BinaryTreeFind(root->right, x);
	if (tmr != NULL)return tmr;
	return NULL;
}

int BinaryTreeComplete(tree* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		int size = QueueSize(&q);
		for (int i = 1; i <= size; i++)
		{
			tree* tmp = QueueFront(&q);
			QueuePop(&q);
			if (tmp == NULL)
			{
				while (!QueueEmpty(&q))
				{
					tree* tp = QueueFront(&q);
					if (tp != NULL)return 0;
					QueuePop(&q);
				}
				return 1;
			}
			
			
			QueuePush(&q, tmp->left);
			QueuePush(&q, tmp->right);
		}
	}
	return 0;
}